package 题目集.倍增算法.lca;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * 货车运输
一共有n座城市，编号1 ~ n
一共有m条双向道路，每条道路(u, v, w)表示有一条限重为w，从u到v的双向道路
从一点到另一点的路途中，汽车载重不能超过每一条道路的限重
每条查询(a, b)表示从a到b的路线中，汽车允许的最大载重是多少
如果从a到b无法到达，那么认为答案是-1
一共有q条查询，返回答案数组
1 <= n <= 10^4
1 <= m <= 5 * 10^4
1 <= q <= 3 * 10^4
0 <= w <= 10^5
1 <= u, v, a, b <= n
测试链接 : https://www.luogu.com.cn/problem/P1967
* 容易想到，需要生成一个最大边生成树。
* 第一思路：先生成最小生成树，然后bfs查找a~b点，记录下载重的最小值
 */
public class ch05_货车运输 {
    static class Reader {
        static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public Reader(Object... o) {
        }

        public int nextInt() {
            try {
                in.nextToken();
            } catch (Exception ignored) {
            }
            return (int) in.nval;
        }
    }
}
